Corelab Seminar
2015-2016
Dimitris Achlioptas
Algorithmic Barriers from Phase Transitions
Abstract.
Constraint Satisfaction Problems (CSPs) are the common abstraction of real-life problems ranging from air-traffic control to protein folding.
Their ubiquity presses forward a fundamental question: why are certain
CSP instances exceptionally hard while other, seemingly similar,
instances are quite easy? To study this phenomenon we consider
probability distributions over CSP instances formed by adding
constraints one-by-one, uniformly and independently. We will see that
for many random CSPs there exists a broad regime in which exponentially
many solutions provably exist, yet all known efficient algorithms fail
to find even one solution. To understand the origin of this algorithmic
barrier we examine how the solution-space geometry evolves as
constraints are added. We prove in a precise mathematical sense that
the barrier faced by algorithms corresponds to a phase transition in
solution-space geometry: at some point, the set of solutions shatters
and goes from resembling a single giant ball to exponentially many
clusters of well-separated solutions. We then discuss the algorithmic
implications of this phenomenon.
Based on joint work with Amin Coja-Oghlan